package data_structure.mooc;

import data_structure.implement.DequeImp;

public class LoopDeque<E> implements DequeImp<E> {

    private E[] data;
    private int front;
    private int tail;
    private int size;

    public LoopDeque(int capacity){
        data=(E[])new Object[capacity];
        size=0;
        tail=0;
        front = 0;
    }
    public LoopDeque(){
        this(10);
    }
    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void addFront(E e) {
        if(getCapacity ()==getSize ()){
            resize (getCapacity ()*2);
        }
        front= front==0?data.length-1:front-1;
        data[front]=e;
        size++;
    }

    @Override
    public void addLast(E e) {
        if(getSize ()==getCapacity ()){
            resize(getCapacity ()*2);
        }
        data[tail]=e;
        tail=(tail+1)%data.length;
        size++;
    }

    private void resize(int capacity){
        E []newData=(E[])new Object[capacity];
        for(int i=0;i<getSize ();i++){
            newData[i]=data[(i+front)%data.length];
        }
        data=newData;
        front=0;
        tail=size;
    }
    @Override
    public E removeFront() {
        if(isEmpty ()){
            throw new IllegalStateException("deque is empty");
        }
        E temp=data[front];
        data[front]=null;
        front= front==data.length-1?0:front+1;
        size--;
        if(getSize ()<=getCapacity ()/4&&getCapacity ()/2!=0){
            resize (getCapacity ()/2);
        }
        return temp;
    }

    @Override
    public E removeLast() {
        if(isEmpty ()){
            throw new IllegalStateException("deque is empty");
        }
        tail= tail==0?data.length-1:tail-1;
        E temp=data[tail];
        data[tail]=null;
        size--;
        if(getSize ()<=getCapacity ()/4&&getCapacity ()/2!=0){
            resize (getCapacity ()/2);
        }
        return temp;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalStateException("deque is empty");
        }
        return data[front];
    }

    @Override
    public E getLast() {

        if (isEmpty()) {
            throw new IllegalStateException("deque is empty");
        }
        int index= tail==0?data.length-1:tail-1;
        return data[index];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public int getCapacity() {
        return data.length;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder ();
        sb.append (String.format ("LoopDeque size=%d capacity=%d", size, getCapacity ()));
        sb.append (" front [");

        for(int i = 0; i < size; i++){
            sb.append (data[(i+front)%data.length]);
            if(i+1!=size){
                sb.append(",");
            }
        }
        sb.append ("] tail");
        return sb.toString ();
    }

     public static void main(String[] args) {

        LoopDeque<Integer>deque=new LoopDeque<Integer> ();
        for(int i=1;i<20;i++){
            if(i%2==0){
                deque.addFront (i);
                System.out.println(deque.toString ());
            }else{
                deque.addLast(i);
                System.out.println(deque.toString ());

            }
        }
        System.out.println("-----------------------");
         for(int i=1;i<20;i++){
            if(i%2==0){
                deque.removeFront ();
                System.out.println(deque.toString ());
            }else{
                deque.removeLast();
                System.out.println(deque.toString ());
            }
        }
    }

}
